{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 大根堆"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {},
   "outputs": [],
   "source": [
    "class MaxHeap(object):\n",
    " \n",
    "    def __init__(self):\n",
    "        self._data = []\n",
    "        self._count = len(self._data)\n",
    " \n",
    "    def size(self):\n",
    "        return self._count\n",
    " \n",
    "    def isEmpty(self):\n",
    "        return self._count == 0\n",
    " \n",
    "    def add(self, item):\n",
    "        # 插入元素入堆\n",
    "        if self._count >= len(self._data):\n",
    "            self._data.append(item)\n",
    "        else:\n",
    "            self._data[self._count] = item\n",
    " \n",
    "        self._count += 1\n",
    "        self._shiftup(self._count-1)\n",
    " \n",
    "    def pop(self):\n",
    "        # 出堆\n",
    "        if self._count > 0:\n",
    "            ret = self._data[0]\n",
    "            self._data[0] = self._data[self._count-1]\n",
    "            self._count -= 1\n",
    "            self._shiftDown(0)\n",
    "            return ret\n",
    "        \n",
    "    def _shiftup(self, index):\n",
    "        # 上移self._data[index]，以使它不大于父节点\n",
    "        parent = (index-1)>>1\n",
    "        while index > 0 and self._data[parent] < self._data[index]:\n",
    "            # swap\n",
    "            self._data[parent], self._data[index] = self._data[index], self._data[parent]\n",
    "            index = parent\n",
    "            parent = (index-1)>>1\n",
    " \n",
    "    def _shiftDown(self, index):\n",
    "        # 下移self._data[index]，以使它不小于子节点\n",
    "        # 左子节点索引\n",
    "        child = (index << 1) + 1\n",
    "        # 有子节点的话就得循环\n",
    "        while child < self._count :\n",
    "            if child+1 < self._count and self._data[child+1] > self._data[child]:\n",
    "                # 有右子节点，将child换成左右节点较大的那个（原先是左节点，+1的话就变成右节点了 ）\n",
    "                child += 1\n",
    "            if self._data[index] >= self._data[child]:\n",
    "                # 当前索引位置已经比两个子节点都大了，不需要交换了\n",
    "                break\n",
    "            self._data[index], self._data[child] = self._data[child], self._data[index]\n",
    "            index = child\n",
    "            child = (index << 1) + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {},
   "outputs": [],
   "source": [
    "heapq=MaxHeap()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {},
   "outputs": [],
   "source": [
    "l=[4,5,1,6,2,7,3,8]\n",
    "for i in l:\n",
    "    heapq.add(i)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[8, 7, 6, 5, 2, 1, 3, 4]"
      ]
     },
     "execution_count": 46,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "heapq._data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "8"
      ]
     },
     "execution_count": 47,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "heapq.size()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[8, 7, 6, 5, 4, 3, 2, 1]"
      ]
     },
     "execution_count": 49,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "[heapq.pop() for i in range(heapq.size())]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Mheap():\n",
    "    \n",
    "    def __init__():\n",
    "        self._data=[]\n",
    "        self._count=len(self._data)\n",
    "        \n",
    "    def pop(item):\n",
    "        self._data.append(item)\n",
    "        self._count+=1\n",
    "        \n",
    "        self._shift_up(item)\n",
    "    \n",
    "    def push():\n",
    "        res=self.pop(0)\n",
    "        \n",
    "        return res\n",
    "    \n",
    "    def _shift_down(item):\n",
    "        \n",
    "    def _shift_up(item):\n",
    "        "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 堆排序"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def heapsort(iterable):\n",
    "    h = []\n",
    "    for value in iterable:\n",
    "        heappush(h, value)\n",
    "    return [heappop(h) for i in range(len(h))]\n",
    "heapsort([1, 3, 5, 7, 9, 2, 4, 6, 8, 0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "排序后\n",
      "5\n",
      "6\n",
      "7\n",
      "11\n",
      "12\n",
      "13\n"
     ]
    }
   ],
   "source": [
    "def heapify(arr, n, i): \n",
    "    largest = i  \n",
    "    l = 2 * i + 1     # left = 2*i + 1 \n",
    "    r = 2 * i + 2     # right = 2*i + 2 \n",
    "  \n",
    "    if l < n and arr[i] < arr[l]: \n",
    "        largest = l \n",
    "  \n",
    "    if r < n and arr[largest] < arr[r]: \n",
    "        largest = r \n",
    "  \n",
    "    if largest != i: \n",
    "        arr[i],arr[largest] = arr[largest],arr[i]  # 交换\n",
    "        heapify(arr, n, largest)\n",
    "\n",
    "def heapSort(arr): \n",
    "    n = len(arr) \n",
    "  \n",
    "    # Build a maxheap. \n",
    "    for i in range(n, -1, -1): \n",
    "        heapify(arr, n, i) \n",
    "  \n",
    "    # 一个个交换元素\n",
    "    for i in range(n-1, 0, -1): \n",
    "        arr[i], arr[0] = arr[0], arr[i]   # 交换\n",
    "        heapify(arr, i, 0) \n",
    "\n",
    "arr = [ 12, 11, 13, 5, 6, 7] \n",
    "heapSort(arr) \n",
    "n = len(arr) \n",
    "print (\"排序后\") \n",
    "for i in range(n): \n",
    "    print (\"%d\" %arr[i]),"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
